package com.cn.test.record;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * description:
 * <p>
 * https://leetcode-cn.com/tag/linked-list/problemset/
 * <p>
 * 递归相关： https://lyl0724.github.io/2020/01/25/1/
 *
 * @author twj
 * @date 2021/7/23 16:40 .
 */
public class OperateNode {

    public static void main(String[] args) {
        ListNode head1 = new ListNode(9);
        ListNode head11 = new ListNode(1, new ListNode(0, new ListNode(1)));
        ListNode head2 = new ListNode(31, new ListNode(5));
        ListNode head3 = new ListNode(122, new ListNode(21212, new ListNode(3333)));
        ListNode head4 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4))));
        ListNode head41 = new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3))));
        ListNode head42 = new ListNode(1, new ListNode(2, new ListNode(2, new ListNode(2, new ListNode(1)))));
        ListNode head5 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
        ListNode head50 = new ListNode(0, new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5))))));
        ListNode head51 = new ListNode(5, new ListNode(4, new ListNode(3, new ListNode(2, new ListNode(1)))));
        ListNode head6 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6))))));
        ListNode head7 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6, new ListNode(7)))))));
        ListNode head8 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6, new ListNode(7, new ListNode(8))))))));
        ListNode head61 = new ListNode(1, new ListNode(1, new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(1, new ListNode(32)))))));
        ListNode head81 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(3, new ListNode(3, new ListNode(4, new ListNode(4, new ListNode(6, new ListNode(7)))))))));

        head1.next = head2;
        ListNode head9 = new ListNode(12, new ListNode(2, new ListNode(3, head1)));
        ListNode[] list = {head3, head2, head6};

//        System.out.println(addTwoNumbers(head1, head2));
//        splitNumber2ListNode(1234);
//        testNodePointer();
//        testremoveNthFromEnd(head5);
//        testmergeTwoLists(head3, head4);
//        testmergeKLists(list);
//        testswapPairs(head7);
//        testrotateRight(head2);
//        testdeleteDuplicates(head9);
//        testdetectCycle(head4);
//        testreorderList(head7);
//        testinsertionSortList(head41);
//        testsortList(head41);
//        testremoveElements(head6);
//        testisPalindrome(head42);
//        testoddEvenList(head5);
//        testswapNodes(head4);
//        testmiddleNode(head6);
//        testgetDecimalValue(head11);
//        testmergeInBetween(head50, head3);
//        testaddTwoNumbersNode(head61, head4);
//        testremoveDuplicateNodes(head81);
//        testreversePrint(head50);
        testgetKthFromEnd(head5);
    }


    private static void testgetKthFromEnd(ListNode head) {
        System.out.println(head);
        ListNode node = getKthFromEnd(head, 2);
        System.out.println(node);
    }

    private static void testreversePrint(ListNode head) {
        System.out.println(head);
        int[] node = reversePrint(head);
        System.out.println(Arrays.toString(node));
    }

    private static void testremoveDuplicateNodes(ListNode head) {
        System.out.println(head);
        ListNode node = removeDuplicateNodes(head);
        System.out.println(node);
    }

    private static void testmergeInBetween(ListNode head, ListNode head2) {
        System.out.println(head);
        System.out.println(head2);
        ListNode node = mergeInBetween(head, 3, 4, head2);
        System.out.println(node);
    }

    private static void testgetDecimalValue(ListNode head) {
        System.out.println(head);
        int node = getDecimalValue(head);
        System.out.println(node);
    }

    private static void testmiddleNode(ListNode head) {
        System.out.println(head);
        ListNode node = middleNode(head);
        System.out.println(node);
    }

    private static void testswapNodes(ListNode head) {
        System.out.println(head);
        ListNode node = swapNodes(head, 3);
        System.out.println(node);
    }

    private static void testaddTwoNumbersNode(ListNode head, ListNode head2) {
        System.out.println(head);
        System.out.println(head2);
        ListNode node = addTwoNumbersNode(head, head2);
        System.out.println(node);
    }

    private static void testoddEvenList(ListNode head) {
        System.out.println(head);
        ListNode node = oddEvenList(head);
        System.out.println(node);
    }

    private static void testdeleteNode(ListNode head, ListNode source) {
        System.out.println(source);
        deleteNode(head);
        System.out.println(source);
    }

    private static void testisPalindrome(ListNode head) {
        System.out.println(head);
        boolean node = isPalindrome(head);
        System.out.println(node);
    }

    private static void testremoveElements(ListNode head) {
        System.out.println(head);
        ListNode node = removeElements(head, 1);
        System.out.println(node);
    }

    private static void testsortList(ListNode head) {
        System.out.println(head);
        ListNode node = sortList(head);
        System.out.println(node);
    }

    private static void testinsertionSortList(ListNode head) {
        System.out.println(head);
        ListNode node = insertionSortList(head);
        System.out.println(node);
    }

    private static void testreorderList(ListNode head) {
        System.out.println(head);
        ListNode node = reorderList(head);
        System.out.println(node);
    }

    private static void testdetectCycle(ListNode head) {
        System.out.println(head);
        ListNode node = detectCycle(head);
        System.out.println(node);
    }

    private static void testreverseBetween(ListNode head) {
        System.out.println(head);
        ListNode node = reverseBetween(head, 2, 4);
        System.out.println(node);
    }

    private static void testreverseKGroup(ListNode head) {
        System.out.println(head);
        ListNode node = reverseKGroup(head, 2);
        System.out.println(node);
    }

    private static void testreverseList(ListNode head) {
        System.out.println(head);
        ListNode node = reverseList(head);
        System.out.println(node);
    }

    private static void testNodePointer() {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6, new ListNode(7)))))));
        ListNode curr = head.next;
        ListNode first = curr;

        System.out.println("---head=->" + head);
        System.out.println("---curr=->" + curr);
        System.out.println("---first=->" + first);

        System.out.println("-------------------1------------------------");
        curr.next = null;
        curr = new ListNode(122, new ListNode(890));

        System.out.println("---head=->" + head);
        System.out.println("---curr=->" + curr);
        System.out.println("---first=->" + first);

        System.out.println("------------------END-------------------------");
        ListNode ans = new ListNode(1);

//        ans.next = head;
//        head = head.next;
//        head = head.next;
//        ListNode next = ans.next;
//        System.out.println(head);
//        System.out.println(next);

//        head = ans;
//        head.next = new ListNode(3);
//        System.out.println(head);
//        head.next = new ListNode(4);
//        System.out.println(head);
//        System.out.println(ans.next);


        head = ans;
        ans.next = new ListNode(666);
        head.next = new ListNode(3);
        System.out.println(ans.next);
        head = new ListNode(2);
        head.next = new ListNode((4));
        System.out.println(ans.next);
    }

    private static void testremoveNthFromEnd(ListNode head) {
        System.out.println(head);
        ListNode node = removeNthFromEnd(head, 2);
        System.out.println(node);
    }

    private static void testswapPairs(ListNode head) {
        System.out.println(head);
        ListNode node = swapPairs(head);
        System.out.println(node);
    }

    private static void testrotateRight(ListNode head) {
        System.out.println(head);
        ListNode node = rotateRight(head, 2);
        System.out.println(node);
    }

    private static void testdeleteDuplicates(ListNode head) {
        System.out.println(head);
        ListNode node = deleteDuplicates(head);
        System.out.println(node);
    }

    private static void testdeleteDuplicate(ListNode head) {
        System.out.println(head);
        ListNode node = deleteDuplicate(head);
        System.out.println(node);
    }

    private static void testmergeTwoLists(ListNode head, ListNode head2) {
        System.out.println(head);
        ListNode node = mergeTwoLists(head, head2);
        System.out.println(node);
    }

    private static void testmergeKLists(ListNode[] list) {
        System.out.println(Arrays.toString(list));
        ListNode node = mergeKLists(list);
        System.out.println(node);
    }

    /**
     * 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
     * k 是一个正整数，它的值小于或等于链表的长度。
     * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
     * 示例：
     * 给你这个链表：1->2->3->4->5
     * 当 k = 1 时，应当返回: 1->2->3->4->5
     * 当 k = 2 时，应当返回: 2->1->4->3->5
     * 当 k = 3 时，应当返回: 3->2->1->4->5
     * <p>
     * <p>
     * 列表中节点的数量在范围 sz 内
     * 1 <= sz <= 5000
     * 0 <= ListNode.val <= 1000
     * 1 <= k <= sz
     *
     * @param head [1,2,3,4,5]
     * @param k    2
     * @return [2, 1, 4, 3, 5]
     * @createby twj on 2021/7/23 17:12
     */
    static ListNode reverseKGroup(ListNode head, int k) {
        if (k <= 1) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode start = dummy;
        ListNode end = head;
        int c = 0;
        while (end != null) {
            c++;
            if (c % k == 0) {
//                end = reverse(start, end.next);
                start = reverse(start, end.next);
                end = start.next;
            } else
                end = end.next;
        }
        return dummy.next;
    }

    /**
     * 1->2->3->4
     * <p>
     * 4->3->2->1
     *
     * @param start
     * @param end
     * @return
     */
    private static ListNode reverse(ListNode start, ListNode end) {
        ListNode curr = start.next;
        ListNode prev = null;
        ListNode first = curr;

        while (curr != end) {
            ListNode tempNext = curr.next;
            curr.next = prev;
            prev = curr;
            curr = tempNext;
        }
        start.next = prev;
        first.next = curr;
        return first;
//        return curr;
    }


    /**
     * 链表反转
     */
    static ListNode reverseList(ListNode head) {

        ListNode pre = null;//前指针节点
        ListNode curr = head;//当前指针节点
        //=每次循环 都将当前节点指向它的前面的节点 然后当前节点和前节点后移
        while (curr != null) {
            ListNode nextTemp = curr.next;//临时节点暂存当前节点的下一个节点 用于后移
            curr.next = pre;//将当前节点指向它前面的的节点
            pre = curr;//前指针后移
            curr = nextTemp;//当前指针后移
        }
        return pre;
    }

    /**
     * https://leetcode-cn.com/problems/add-two-numbers/
     * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
     * 请你将两个数相加，并以相同形式返回一个表示和的链表。
     * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     * <p>
     * 每个链表中的节点数在范围 [1, 100] 内
     * 0 <= ListNode.val <= 9
     * 题目数据保证列表表示的数字不含前导零
     * <p>
     * 输入：n1 = [9,9,9,9,9,9,9], n2 = [9,9,9,9]
     * 输出：[8,9,9,9,0,0,0,1]
     *
     * @param n1 [2,4,3]
     * @param n2 [5,6,4]
     * @return [7, 0, 8]      解释：342 + 465 = 807.
     * @createby twj on 2021/8/3 9:14
     * [9]
     * [1,9,9,9,9,9,9,9,9,9]失败
     */
    static ListNode addTwoNumbers(ListNode n1, ListNode n2) {
        int k = 0, k1 = 0;
        int sum0 = 0, sum2 = 0;
        while (n1 != null) {
            double pow = Math.pow(10, k++);
            sum0 += n1.val * pow;
            n1 = n1.next;
        }
        while (n2 != null) {
            double pow = Math.pow(10, k1++);
            sum2 += n2.val * pow;
            n2 = n2.next;
        }
        //分解数字成链表
        ListNode n = splitNumber2ListNode(sum0 + sum2);
        return n;
    }

    static ListNode addTwoNumbers3(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        l2.val = l1.val + l2.val;
        if (l2.val >= 10) {
            l2.val = l2.val % 10;
            if (l2.next != null) {
                l2.next.val = l2.next.val + 1;
                if (l2.next.val == 10) {
                    l2.next = addTwoNumbers3(new ListNode(0, null), l2.next);
                }
            } else {
                l2.next = new ListNode(1, null);
            }
        }
        l2.next = addTwoNumbers3(l1.next, l2.next);
        return l2;
    }

    /**
     * 同 #addTwoNumbers(ListNode n1, ListNode n2)
     * 解法2
     */
    static ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        ListNode root = new ListNode(0);
        ListNode cursor = root;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            int l1Val = l1 != null ? l1.val : 0;
            int l2Val = l2 != null ? l2.val : 0;
            int sumVal = l1Val + l2Val + carry;
            carry = sumVal / 10;

            cursor.next = new ListNode(sumVal % 10);
            cursor = cursor.next;

            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        return root.next;
    }

    /**
     * @param number 123
     * @return 3->2->1
     * @createby twj on 2021/8/3 15:18
     */
    private static ListNode splitNumber2ListNode(int number) {
        ListNode head = new ListNode(0);
        ListNode cursor = head;
        if (number <= 0) return head;
        while (number != 0) {
            int val = number % 10;

            ListNode curr = new ListNode(val);
//            curr.next = head.next;
//            head.next = curr;
            cursor.next = curr;
            cursor = curr;
            number = number / 10;
        }
        System.out.println(head);

        return head.next;
    }

    /**
     * https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
     * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
     * <p>
     * 输入：head = [1,2,3,4,5], n = 2
     * 输出：[1,2,3,5]
     * <p>
     * 输入：head = [1], n = 1
     * 输出：[]
     * <p>
     * 输入：head = [1,2], n = 1
     * 输出：[1]
     * <p>
     * 提示：
     * 链表中结点的数目为 sz
     * 1 <= sz <= 30
     * 0 <= ListNode.val <= 100
     * 1 <= n <= sz
     *
     * @param head
     * @param n
     * @return
     * @createby twj on 2021/8/5 14:25
     */
    static ListNode removeNthFromEnd(ListNode head, int n) {
//        方法1
//        return removeNode(head, n) == n ? head.next : head;

//        方法2
//        ListNode cursor = head;
//        int count = 0;
//        while (cursor != null) {
//            count++;
//            cursor = cursor.next;
//        }
//        //  正数第curr个
//        int curr = count - n;
//        if (curr==0) return head.next;// 删除第一个
//        count = 0;
//        ListNode currN = new ListNode(0);
//        currN.next = head;
//
//        while (currN != null) {
//            currN = currN.next;
//            if (++count == curr) currN.next = currN.next.next;
//        }
//        return head;

//        方法3 双指针
        ListNode p1 = head;
        ListNode p2 = head;
        //快指针前进N步
        while (n-- > 0) {
            p2 = p2.next;
        }
        //判断倒数第n个节点是不是头结点
        if (p2 == null) {
            return head.next;
        }
        //判断倒数第n个节点不是头结点，找到倒数第n个节点的前一个节点
        while (p2.next != null) {
            p2 = p2.next;
            p1 = p1.next;
        }
        //删除倒数第n个节点
        ListNode temp = (p1.next).next;
        p1.next = temp;
        return head;
    }

    /**
     * https://leetcode-cn.com/problems/merge-two-sorted-lists/
     * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
     * <p>
     * 输入：l1 = [1,2,4], l2 = [1,3,4]
     * 输出：[1,1,2,3,4,4]
     * <p>
     * 输入：l1 = [], l2 = []
     * 输出：[]
     * <p>
     * 输入：l1 = [], l2 = [0]
     * 输出：[0]
     * <p>
     * 提示：
     * 两个链表的节点数目范围是 [0, 50]
     * -100 <= ListNode.val <= 100
     * l1 和 l2 均按 非递减顺序 排列
     *
     * @param p1
     * @param p2
     * @return
     * @createby twj on 2021/8/5 16:23
     */
    static ListNode mergeTwoLists(ListNode p1, ListNode p2) {
//        方法一
//        return mergeTwoLists2(p1, p2);
//        方法二
        //空间换时间
        ListNode head = new ListNode(0);
        ListNode curr = head;
        while (p1 != null && p2 != null) {
            if (p1.val <= p2.val) {
                curr.next = p1;
                curr = curr.next;
                p1 = p1.next;
            } else {
                curr.next = p2;
                curr = curr.next;
                p2 = p2.next;
            }
        }
        if (p1 != null) {
            curr.next = p1;
        } else {
            curr.next = p2;
        }
        return head.next;
    }

    /**
     * https://leetcode-cn.com/problems/merge-k-sorted-lists/
     * 给你一个链表数组，每个链表都已经按升序排列。
     * <p>
     * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
     * <p>
     * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
     * 输出：[1,1,2,3,4,4,5,6]
     * 解释：链表数组如下：
     * [
     * 1->4->5,
     * 1->3->4,
     * 2->6
     * ]
     * 将它们合并到一个有序链表中得到。
     * 1->1->2->3->4->4->5->6
     * <p>
     * 输入：lists = []
     * 输出：[]
     * <p>
     * 输入：lists = [[]]
     * 输出：[]
     * <p>
     * 提示：
     * k == lists.length
     * 0 <= k <= 10^4
     * 0 <= lists[i].length <= 500
     * -10^4 <= lists[i][j] <= 10^4
     * lists[i] 按 升序 排列
     * lists[i].length 的总和不超过 10^4
     *
     * @createby twj on 2021/8/6 16:07
     */
    static ListNode mergeKLists(ListNode[] lists) {
        int length = lists.length;
        if (lists == null || length < 1) {
            return null;
        }
        if (length == 1) {
            return lists[0];
        }
        if (length == 2) {
            return mergeTwoLists(lists[0], lists[1]);
        }
        //else {//(length > 2)
//            ListNode node = mergeTwoLists(lists[0], lists[1]);
//            for (int i = 2; i < length; i++) {
//                node = mergeTwoLists(node, lists[i]);
//            }
//            return node;
//        }

        //归并法    1 ms  39.8 MB
        int mid = length / 2;
        ListNode[] lefts = new ListNode[mid];
        for (int i = 0; i < mid; i++) {
            lefts[i] = lists[i];
        }
        ListNode[] rights = new ListNode[length - mid];
        for (int i = mid, j = 0; i < length; i++, j++) {
            rights[j] = lists[i];
        }
        return mergeTwoLists(mergeKLists(lefts), mergeKLists(rights));
    }

    /**
     * mergeTwoLists递归法
     */
    static ListNode mergeTwoLists2(ListNode l1, ListNode l2) {

        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode res = l1.val < l2.val ? l1 : l2;
        res.next = mergeTwoLists2(res.next, l1.val >= l2.val ? l1 : l2);
        return res;
    }


    static int removeNode(ListNode node, int n) {
        if (node.next == null) return 1;
        int m = removeNode(node.next, n);
        if (m == n)
            if (m == 1) node.next = null;
            else node.next = node.next.next;
        return m + 1;
    }

    /**
     * https://leetcode-cn.com/problems/swap-nodes-in-pairs/
     * 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
     * <p>
     * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
     * <p>
     * 输入：head = [1,2,3,4]
     * 输出：[2,1,4,3]
     * <p>
     * 输入：head = []
     * 输出：[]
     * <p>
     * 输入：head = [1]
     * 输出：[1]
     * <p>
     * 提示：
     * 链表中节点的数目在范围 [0, 100] 内
     * 0 <= Node.val <= 100
     * <p>
     * 进阶：你能在不修改链表节点值的情况下解决这个问题吗?（也就是说，仅修改节点本身。）
     *
     * @createby twj on 2021/8/6 17:29
     */
    static ListNode swapPairs(ListNode head) {
//        指针交换
        return swapPairs2(head);
//    方法2  值交换
//        ListNode dummy = new ListNode(0);
//        dummy.next = head;
//        ListNode curr = head;
//        int c = 0;
//        ListNode pre = dummy;
//        while (curr != null) {
//            c++;
//            if (c % 2 == 0) {
//                int temp=curr.val;
//                curr.val=pre.val;
//                pre.val=temp;
//
//            }
//            pre=pre.next;
//            curr = curr.next;
//        }
//        return head;
    }

    /**
     * https://leetcode-cn.com/problems/rotate-list/
     * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
     * <p>
     * 输入：head = [1,2,3,4,5], k = 2
     * 输出：[4,5,1,2,3]
     * <p>
     * 输入：head = [0,1,2], k = 4
     * 输出：[2,0,1]
     * <p>
     * 提示：     *
     * 链表中节点的数目在范围 [0, 500] 内
     * -100 <= Node.val <= 100
     * 0 <= k <= 2 * 109
     *
     * @createby twj on 2021/8/9 17:49
     */
    static ListNode rotateRight(ListNode head, int k) {
//       方法2
        return rotateRight2(head, k);
//        方法1
/*        if (head == null ) return head;
        ListNode curr = head;
        ListNode mid = new ListNode(-1000);
        mid.next = head;
        ListNode pre = mid;
        int len = 0;
        while (curr != null) {
            curr = curr.next;
            pre = pre.next;
            len++;
        }
        pre.next = mid;//构造环
        ListNode p = mid;
        int c;
        if (len > k) {
            c = len - k;//链表头
        } else {
            c = len - (k % len);
        }
        for (int i = 0; i < c; i++) p = p.next;
        ListNode start = p.next;
        p.next = null;//破环
        ListNode first = start;
//        剔除掉mid节点
        while (first != null && first.next != null) {
//            第一个节点是mid
            if (first.val == mid.val) {
                return mid.next;
            }
//            第二个节点
            if (first.next.val == mid.val) {
                first.next = first.next.next;
                return start;
            }
//            游标
            first = first.next;
        }
        return start;*/
    }

    static ListNode rotateRight2(ListNode head, int k) {
        if (k <= 0 || head == null) return head;
        // 1. calculate ListNode length
        ListNode cur = head;
        ListNode last = head;
        int len = 0;
        while (cur != null) {
            len++;
            if (cur.next == null) last = cur;
            cur = cur.next;
        }
        // 2. cut
        int cutLen = k % len;
        if (cutLen == 0) return head;
        ListNode preHead = head;
        cur = head;
        for (int i = 1; i < len - cutLen; i++) {
            cur = cur.next;
        }
        head = cur.next;
        cur.next = null;// cut
        // 3. connect
        last.next = preHead;
        return head;
    }

    static ListNode swapPairs2(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode curr = head;
        while (curr != null && curr.next != null) {
            ListNode temp = curr.next;
            curr.next = curr.next.next;
            temp.next = curr;
            prev.next = temp;
            prev = curr;
            curr = curr.next;
        }
        return dummy.next;
    }

    /**
     * https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/
     * 存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，
     * 只保留原始链表中 没有重复出现 的数字。
     * 返回同样按升序排列的结果链表。
     * <p>
     * 输入：head = [1,2,3,3,4,4,5]
     * 输出：[1,2,5]
     * <p>
     * 输入：head = [1,1,1,2,3]
     * 输出：[2,3]
     * <p>
     * 提示：
     * 链表中节点数目在范围 [0, 300] 内
     * -100 <= Node.val <= 100
     * 题目数据保证链表已经按升序排列
     *
     * @createby twj on 2021/8/10 17:48
     */
    static ListNode deleteDuplicates(ListNode head) {
        return deleteDuplicates2(head);
//        方法2
//        if (head == null) return head;
//        ListNode dummy = new ListNode(-1000);
//        dummy.next = head;
//        ListNode pre = dummy;
//        ListNode first = head;
//        ListNode second = head.next;
//        while ( second != null) {
//            if (first.val == second.val) {
////                连续相同的值
//                while (second != null  && first.val == second.val) {
//                    second = second.next;
//                }
//                first = second;
//            } else {
//                pre.next = first;
//                pre = pre.next;
//                first = second;
//            }
//            if (second ==null) break;
//            second = second.next;
//        }
//        pre.next = first;
//        return dummy.next;
    }

    private static ListNode deleteDuplicates2(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode next = head.next;
        if (head.val == next.val) {
//            1     1 --> 1 --> 1 --> 2 --> 3
            while (next != null && head.val == next.val) next = next.next;
//            2
            head = deleteDuplicates2(next);
        } else {
//            3
            head.next = deleteDuplicates2(next);
        }
        return head;
    }

    /**
     * https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
     * https://lyl0724.github.io/2020/01/25/1/
     * 存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。
     * <p>
     * 返回同样按升序排列的结果链表。
     * <p>
     * 输入：head = [1,1,2]
     * 输出：[1,2]
     * <p>
     * 输入：head = [1,1,2,3,3]
     * 输出：[1,2,3]
     * <p>
     * 提示：
     * <p>
     * 链表中节点数目在范围 [0, 300] 内
     * -100 <= Node.val <= 100
     * 题目数据保证链表已经按升序排列
     *
     * @createby twj on 2021/8/12 9:52
     */
    static ListNode deleteDuplicate(ListNode head) {
        ListNode dummy = new ListNode(-101);
        dummy.next = head;
        ListNode curr = head;
        while (curr != null && curr.next != null) {
            if (curr.val == curr.next.val)
                curr.next = curr.next.next;
            else
                curr = curr.next;
        }
        return dummy.next;
    }

    /**
     * https://leetcode-cn.com/problems/reverse-linked-list-ii/
     * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。
     * 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
     * <p>
     * 输入：head = [1,2,3,4,5], left = 2, right = 4
     * 输出：[1,4,3,2,5]
     * <p>
     * 输入：head = [5], left = 1, right = 1
     * 输出：[5]
     * <p>
     * <p>
     * 提示：
     * 链表中节点数目为 n
     * 1 <= n <= 500
     * -500 <= Node.val <= 500
     * 1 <= left <= right <= n
     *
     * @createby twj on 2021/8/12 10:41
     */
    static ListNode reverseBetween(ListNode head, int left, int right) {

        if (head == null || head.next == null || left == right) return head;
        ListNode pre = new ListNode(-1000);
        pre.next = head;
        ListNode dummy = pre;
        ListNode curr = head;
//        找到开始反转节点和他前一个节点
        for (int i = 1; i < left; i++) {
            curr = curr.next;
            pre = pre.next;
        }
        ListNode start = curr;
//      找到反转结束节点
        for (int i = left; i < right; i++) {
            curr = curr.next;
        }
        ListNode end = curr;
        pre.next = reverse2(start, end.next);
        return dummy.next;
    }

    private static ListNode reverse2(ListNode start, ListNode end) {
        ListNode curr = start;
//        前驱节点指向end节点
        ListNode prev = end;
        while (curr != end) {
            ListNode tempNext = curr.next;
            curr.next = prev;
            prev = curr;
            curr = tempNext;
        }
        return prev;
    }

    /**
     * https://leetcode-cn.com/problems/linked-list-cycle/
     * 给定一个链表，判断链表中是否有环。
     * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
     * 如果链表中存在环，则返回 true 。 否则，返回 false 。
     * <p>
     * 输入：head = [3,2,0,-4], pos = 1
     * 输出：true
     * 解释：链表中有一个环，其尾部连接到第二个节点。
     * <p>
     * 输入：head = [1,2], pos = 0
     * 输出：true
     * 解释：链表中有一个环，其尾部连接到第一个节点。
     * <p>
     * 输入：head = [1], pos = -1
     * 输出：false
     * 解释：链表中没有环。
     * <p>
     * 提示：
     * <p>
     * 链表中节点的数目范围是 [0, 104]
     * -105 <= Node.val <= 105
     * pos 为 -1 或者链表中的一个 有效索引 。
     *
     * @createby twj on 2021/8/12 16:53
     */
    static boolean hasCycle(ListNode head) {

        if (head == null || head.next == null || head.next.next == null) return false;
        ListNode curr = head;
        ListNode next = head.next.next;
        while (curr != next) {
            curr = curr.next;
            if (curr == null || next == null) return false;
            next = next.next;
            if (next == null) return false;
            next = next.next;

//            way 2
//            try{
//                curr = curr.next;
//                next = next.next.next;
//            }catch(Exception e){
//                return false;
//            }
        }
        return true;
    }

    /**
     * https://leetcode-cn.com/problems/linked-list
     * https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/xiang-xi-tu-jie-ken-ding-kan-de-ming-bai-by-xixili/-cycle-ii/
     * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
     * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
     * 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
     * <p>
     * 说明：不允许修改给定的链表。
     * 进阶： 你是否可以使用 O(1) 空间解决此题？
     * <p>
     * 输入：head = [3,2,0,-4], pos = 1
     * 输出：返回索引为 1 的链表节点
     * 解释：链表中有一个环，其尾部连接到第二个节点
     * <p>
     * 输入：head = [1,2], pos = 0
     * 输出：返回索引为 0 的链表节点
     * 解释：链表中有一个环，其尾部连接到第一个节点。
     * <p>
     * 输入：head = [1], pos = -1
     * 输出：返回 null
     * 解释：链表中没有环。
     * <p>
     * 提示：
     * 链表中节点的数目范围在范围 [0, 104] 内
     * -105 <= Node.val <= 105
     * pos 的值为 -1 或者链表中的一个有效索引
     *
     * @createby twj on 2021/8/13 8:48
     */
    static ListNode detectCycle(ListNode head) {

        if (head == null || head.next == null || head.next.next == null) return null;
        Set<ListNode> set = new HashSet<ListNode>();
        ListNode curr = head;
        while (curr != null) {
            if (set.add(curr)) {
                curr = curr.next;
            } else {
                return curr;
            }
        }
        return null;
//        way 2
//        ListNode fast = head, slow = head;
//        while (true) {
//            if (fast == null || fast.next == null) return null;
//            fast = fast.next.next;
//            slow = slow.next;
//            if (fast == slow) break;
//        }
//        fast = head;
//        while (slow != fast) {
//            slow = slow.next;
//            fast = fast.next;
//        }
//        return fast;

    }

    /**
     * https://leetcode-cn.com/problems/reorder-list/
     * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
     * <p>
     *  L0 → L1 → … → Ln-1 → Ln 
     * 请将其重新排列后变为：
     * <p>
     * L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
     * <p>
     * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
     * <p>
     * 输入: head = [1,2,3,4]
     * 输出: [1,4,2,3]
     * <p>
     * 输入: head = [1,2,3,4,5]
     * 输出: [1,5,2,4,3]
     * <p>
     * 提示：
     * 链表的长度范围为 [1, 5 * 104]
     * 1 <= node.val <= 1000
     *
     * @createby twj on 2021/8/13 14:22
     */
    static ListNode reorderList(ListNode head) {
//        方法1  1递归next找到尾结点 2切下尾结点 3拼接到首节点 4返到1
//        ListNode next = head.next;
//        ListNode pre = head;
//        ListNode curr = head;
//        while (next != null && next.next!=null) {
//            ListNode tail = tail(pre, next);
//            curr.next = tail;
//            tail.next = next;
//            curr = next;
//            pre = next;
//            next = next.next;
//        }
//        方法二 快慢指针找到切点 2后半段反转 3 依次插入
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode fast = dummy, slow = dummy;
        ListNode curr = head;
        while (slow != null && fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode start = slow.next;
        slow.next = null;//切断
        start = reverseList(start);
        while (start != null) {
            ListNode temp = curr.next;
            ListNode startTemp = start.next;
            curr.next = start;
            start.next = temp;
            curr = temp;
            start = startTemp;
        }
        return head;
    }

    private static ListNode tail(ListNode pre, ListNode curr) {
        if (curr == null) return curr;
        if (curr.next == null) {
            pre.next = null;  //切断最后前一个节点
            return curr;
        } else
            return tail(curr, curr.next);
    }

    /**
     * https://leetcode-cn.com/problems/insertion-sort-list/
     * 解法1 https://leetcode-cn.com/problems/insertion-sort-list/solution/java-dai-zhu-shi-by-xinyang-k-fpc7/
     * 对链表进行插入排序。
     * 插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
     * 每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
     * <p>
     *  
     * <p>
     * 插入排序算法：
     * <p>
     * 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
     * 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
     * 重复直到所有输入数据插入完为止。
     * <p>
     * 输入: 4->2->1->3
     * 输出: 1->2->3->4
     * <p>
     * 输入: -1->5->3->4->0
     * 输出: -1->0->3->4->5
     *
     * @createby twj on 2021/8/17 10:40
     */
    private static ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(-10000);
        dummy.next = head;
        ListNode start = dummy, curr = start.next, next = curr.next;
        while (next != null) {
            if (next.val < curr.val) {                  // 下一个节点比当前小的时候 进行插入
                curr.next = next.next;                    //连接未比较的
                ListNode startNext = start.next;    //     起始节点下一个（小循环中的）  startNext设为变量
                while (start != curr) {
                    if (next.val < startNext.val) {
                        start.next = next;
                        next.next = startNext;
                        next = curr.next;           // 设置（后移）新的 next节点
                        break;
                    } else {
                        start = startNext;
                        startNext = startNext.next;
                    }
                }
                start = dummy;  //     重置起始节点
            } else {
                curr = next;
                next = next.next;
            }
        }
        return dummy.next;
    }

    /**
     * https://leetcode-cn.com/problems/sort-list/
     * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
     * <p>
     * 进阶：
     * <p>
     * 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
     *  
     * 输入：head = [4,2,1,3]
     * 输出：[1,2,3,4]
     * <p>
     * 输入：head = [-1,5,3,4,0]
     * 输出：[-1,0,3,4,5]
     * <p>
     * 输入：head = []
     * 输出：[]
     * <p>
     * 提示：
     * 链表中节点的数目在范围 [0, 5 * 104] 内
     * -105 <= Node.val <= 105
     *
     * @createby twj on 2021/8/18 14:27
     */
    static ListNode sortList(ListNode head) {
        return sortList(head, null);
    }

    static ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) {
            return head;
        }
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode slow = head, fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode listNode1 = sortList(head, mid);
        ListNode listNode2 = sortList(mid, tail);
        ListNode sorted = mergeSortNode(listNode1, listNode2);
        return sorted;
    }

    private static ListNode mergeSortNode(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(-1000);
        ListNode temp = dummy, temp1 = head1, temp2 = head2;
        while (temp1 != null && temp2 != null) {
            if (temp1.val <= temp2.val) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if (temp1 != null) {
            temp.next = temp1;
        } else if (temp2 != null) {
            temp.next = temp2;
        }
        return dummy.next;
    }

    /**
     * https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
     * <p>
     * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
     * 题目数据 保证 整个链式结构中不存在环。
     * <p>
     * 注意，函数返回结果后，链表必须 保持其原始结构 。
     * <p>
     * 提示：
     * <p>
     * listA 中节点数目为 m
     * listB 中节点数目为 n
     * 0 <= m, n <= 3 * 104
     * 1 <= Node.val <= 105
     * 0 <= skipA <= m
     * 0 <= skipB <= n
     * 如果 listA 和 listB 没有交点，intersectVal 为 0
     * 如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]
     *
     * @createby twj on 2021/8/19 14:44
     */
    static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//        方法1
//        Set<ListNode> set = new HashSet<>();
//        while (headA != null) {
//            set.add(headA);
//            headA = headA.next;
//        }
//        while (headB != null) {
//            if (!set.add(headB)) {
//                return headB;
//            }
//            headB = headB.next;
//        }
//        return null;

//        方法2    (m+c) + n = (n+c) + m  c是共同距离， n m 各自距离
        if (headA == null || headB == null) return null;
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }

    /**
     * https://leetcode-cn.com/problems/remove-linked-list-elements/
     * 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
     * <p>
     * 输入：head = [1,2,6,3,4,5,6], val = 6
     * 输出：[1,2,3,4,5]
     * <p>
     * 输入：head = [], val = 1
     * 输出：[]
     * <p>
     * 输入：head = [7,7,7,7], val = 7
     * 输出：[]
     * <p>
     * 提示：
     * <p>
     * 列表中的节点数目在范围 [0, 104] 内
     * 1 <= Node.val <= 50
     * 0 <= val <= 50
     *
     * @createby twj on 2021/8/19 16:20
     */
    static ListNode removeElements(ListNode head, int val) {
        if (head == null) return null;
        ListNode dummy = new ListNode(-1000);
        dummy.next = head;
        ListNode pre = dummy;
//        ListNode curr = head;
//        while (curr != null) {
//            if (curr.val == val) {
//                ListNode temp = curr.next;
//                pre.next = temp;
//                curr = temp;
//                continue;
//            }
//            pre = pre.next;
//            curr = curr.next;
//        }
        while (pre.next != null) {
            if (pre.next.val == val) {
                pre.next = pre.next.next;
                continue;
            }
            pre = pre.next;
        }
        return dummy.next;
//        方法2 递归
//        if (head == null)
//            return head;
//        head.next = removeElements(head.next, val);
//        return head.val == val ? head.next : head;
    }

    /**
     * https://leetcode-cn.com/problems/palindrome-linked-list/
     * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
     * <p>
     * 输入：head = [1,2,2,1]
     * 输出：true
     * <p>
     * 输入：head = [1,2]
     * 输出：false
     * <p>
     * 提示：
     * <p>
     * 链表中节点数目在范围[1, 105] 内
     * 0 <= Node.val <= 9
     *
     * @createby twj on 2021/8/19 16:59
     */
    static boolean isPalindrome(ListNode head) {
//        1快慢指针找到中点  2反转后半部分链表 3和前半部分比较值不一样就不是
        if (head == null) return false;
        if (head.next == null) return true;
        ListNode slow = head, fast = head.next;
        if (fast.next == null && slow.val != fast.val) return false;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        fast = reverseList(slow);
        slow = head;
        while (slow != null) {
            if (slow.val == fast.val) {
                slow = slow.next;
                fast = fast.next;
            } else
                return false;
        }
        return true;

    }

    /**
     * https://leetcode-cn.com/problems/delete-node-in-a-linked-list/
     * 请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。
     * <p>
     * 输入：head = [4,5,1,9], node = 5
     * 输出：[4,1,9]
     * <p>
     * 输入：head = [4,5,1,9], node = 1
     * 输出：[4,5,9]
     * 提示：
     * 链表至少包含两个节点。
     * 链表中所有节点的值都是唯一的。
     * 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
     * 不要从你的函数中返回任何结果。
     *
     * @createby twj on 2021/8/20 8:47
     */
    static void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }

    /**
     * https://leetcode-cn.com/problems/odd-even-linked-list/
     * 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
     * <p>
     * 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
     * <p>
     * 输入: 1->2->3->4->5->NULL
     * 输出: 1->3->5->2->4->NULL
     * <p>
     * 输入: 2->1->3->5->6->4->7->NULL
     * 输出: 2->3->6->7->1->5->4->NULL
     * <p>
     * 说明:
     * 应当保持奇数节点和偶数节点的相对顺序。
     * 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。
     *
     * @createby twj on 2021/8/20 10:36
     */
    static ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode js = head, osHead = head.next, os = osHead;
        while (os != null && os.next != null) {
            js.next = os.next;
            js = js.next;
            os.next = js.next;
            os = os.next;
        }
        js.next = osHead;
        return head;
    }

    /**
     * https://leetcode-cn.com/problems/add-two-numbers-ii/
     * 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。
     * 它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
     * <p>
     * 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
     * <p>
     * 输入：l1 = [7,2,4,3], l2 = [5,6,4]
     * 输出：[7,8,0,7]
     * <p>
     * 输入：l1 = [2,4,3], l2 = [5,6,4]
     * 输出：[8,0,7]
     * <p>
     * 输入：l1 = [0], l2 = [0]
     * 输出：[0]
     * <p>
     * 提示：
     * <p>
     * 链表的长度范围为 [1, 100]
     * 0 <= node.val <= 9
     * 输入数据保证链表代表的数字无前导 0
     *
     * @createby twj on 2021/8/20 15:20
     */
    static ListNode addTwoNumbersNode(ListNode l1, ListNode l2) {
//        反转 ＋
        l1 = reverseList(l1);
        l2 = reverseList(l2);
        ListNode c1 = l1, c2 = l2;
        ListNode sum = new ListNode(-1);
        ListNode newNode = sum;
        int carry = 0;
        while (c1 != null || c2 != null || carry != 0) {
            int vc1 = c1 != null ? c1.val : 0;
            int vc2 = c2 != null ? c2.val : 0;

            int s = vc1 + vc2 + carry;
            carry = s / 10;
            newNode.next = new ListNode(s % 10);
            newNode = newNode.next;
            if (c1 != null) c1 = c1.next;
            if (c2 != null) c2 = c2.next;
        }
//        while (c1 != null) {
//            int s = c1.val + carry;
//            carry = s / 10;
//            newNode.next = new ListNode(carry > 0 ? s % 10 : s);
//            newNode = newNode.next;
//            c1 = c1.next;
//        }
//        while (c2 != null) {
//            int s = c2.val + carry;
//            carry = s / 10;
//            newNode.next = new ListNode(carry > 0 ? s % 10 : s);
//            newNode = newNode.next;
//            c2 = c2.next;
//        }
//        //最后进位
//        if (carry > 0)
//            newNode.next = new ListNode(carry);
        return reverseList(sum.next);
    }

    /**
     * https://leetcode-cn.com/problems/swapping-nodes-in-a-linked-list/
     * <p>
     * 给你链表的头节点 head 和一个整数 k 。
     * 交换 链表正数第 k 个节点和倒数第 k 个节点的值后，返回链表的头节点（链表 从 1 开始索引）
     * 输入：head = [1,2,3,4,5], k = 2
     * 输出：[1,4,3,2,5]
     * <p>
     * 输入：head = [7,9,6,6,7,8,3,0,9,5], k = 5
     * 输出：[7,9,6,6,8,7,3,0,9,5]
     * <p>
     * 输入：head = [1], k = 1
     * 输出：[1]
     * <p>
     * 输入：head = [1,2], k = 1
     * 输出：[2,1]
     * <p>
     * 输入：head = [1,2,3], k = 2
     * 输出：[1,2,3]
     * <p>
     * 提示：
     * 链表中节点的数目是 n
     * 1 <= k <= n <= 105
     * 0 <= Node.val <= 100
     *
     * @createby twj on 2021/8/23 9:18
     */
    static ListNode swapNodes(ListNode head, int k) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode curr = head;
        int count = 0;
        while (curr != null) {
            ++count;
            curr = curr.next;
        }
        int i = count - k;// 倒数i个，，  (k-1)==i  居中
        if (count <= 1 || ((k - 1) == i)) return head;
        curr = dummy;
        ListNode pre1 = dummy, pre2 = dummy;
        for (int j = 0; j <= count; j++) {
            if (j == (k - 1)) pre1 = curr;
            if (j == i) pre2 = curr;
            curr = curr.next;
        }
//        方法1 值交换
        int temp = pre1.next.val;
        pre1.next.val = pre2.next.val;
        pre2.next.val = temp;
        return head;

//       方法2节点交换
//        ListNode swap1 = pre1.next;
//        ListNode swap2 = pre2.next;
//        ListNode st1 = swap1.next;
//        ListNode st2 = swap2.next;
//        if (pre1.next == pre2) {//相邻交换 1 2 3 4  k=2
//            pre1.next = swap2;
//            swap2.next = swap1;
//            swap1.next = st2;
//        } else if (pre2.next == pre1) {
//            pre2.next=swap1;
//            swap1.next=swap2;
//            swap2.next=st1;
//        } else {
//            pre1.next = swap2;
//            swap2.next = st1;
//            pre2.next = swap1;
//            swap1.next = st2;
//        }
//        return dummy.next;
    }

    /**
     * https://leetcode-cn.com/problems/middle-of-the-linked-list
     * 给定一个头结点为 head 的非空单链表，返回链表的中间结点。
     * 如果有两个中间结点，则返回第二个中间结点。
     * <p>
     * 输入：[1,2,3,4,5,6]
     * 输出：此列表中的结点 4 (序列化形式：[4,5,6])
     * 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
     * <p>
     * 输入：[1,2,3,4,5]
     * 输出：此列表中的结点 3 (序列化形式：[3,4,5])
     * 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
     * 注意，我们返回了一个 ListNode 类型的对象 ans，这样：
     * ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
     *
     * @createby twj on 2021/8/23 15:01
     */
    static ListNode middleNode(ListNode head) {

        ListNode slow = head, fast = head.next;
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
            if (fast != null)
                fast = fast.next;
        }
        return slow;
    }

    /**
     * https://leetcode-cn.com/problems/convert-binary-number-in-a-linked-list-to-integer
     * 给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。
     * <p>
     * 请你返回该链表所表示数字的 十进制值 。
     * <p>
     * 输入：head = [1,0,1]
     * 输出：5
     * 解释：二进制数 (101) 转化为十进制数 (5)
     * <p>
     * 输入：head = [0]
     * 输出：0
     * <p>
     * 输入：head = [1]
     * 输出：1
     * <p>
     * 输入：head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
     * 输出：18880
     * 提示：
     * 链表不为空。
     * 链表的结点总数不超过 30。
     * 每个结点的值不是 0 就是 1。
     *
     * @createby twj on 2021/8/23 16:20
     */
    static int getDecimalValue(ListNode head) {

        int c = 0, sum = 0;
        ListNode curr = head;
        while (curr != null) {
            c++;
            curr = curr.next;
        }
        curr = head;
        for (int i = c - 1; i >= 0; i--) {
            sum += curr.val * Math.pow(2, i);
            curr = curr.next;
        }
        return sum;
    }

    /**
     * https://leetcode-cn.com/problems/merge-in-between-linked-lists
     * 给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。
     * <p>
     * 请你将 list1 中第 a 个节点到第 b 个节点删除，并将list2 接在被删除节点的位置。
     * <p>
     * 输入：list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
     * 输出：[0,1,2,1000000,1000001,1000002,5]
     * 解释：我们删除 list1 中第三和第四个节点，并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。
     * <p>
     * 提示：
     * 3 <= list1.length <= 104
     * 1 <= a <= b < list1.length - 1
     * 1 <= list2.length <= 104
     *
     * @createby twj on 2021/8/25 16:11
     */
    static ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode curr = list1;
        ListNode temp;
        int c = 0;
        for (int i = 0; i < b; i++) {
            if (++c == a) {
                temp = curr.next;
                curr.next = list2;
                curr = temp;

            } else curr = curr.next;
        }
        ListNode curr2 = list2;
//        最后一个节点
        while (curr2.next != null) {
            curr2 = curr2.next;
        }
        curr2.next = curr.next;
        return list1;
    }

    /**
     * https://leetcode-cn.com/problems/remove-duplicate-node-lcci/
     * 编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
     * 输入：[1, 2, 3, 3, 2, 1]
     * 输出：[1, 2, 3]
     * <p>
     * 输入：[1, 1, 1, 1, 2]
     * 输出：[1, 2]
     * <p>
     * 提示：
     * 链表长度在[0, 20000]范围内。
     * 链表元素在[0, 20000]范围内。
     *
     * @createby twj on 2021/8/25 17:00
     */
    static ListNode removeDuplicateNodes(ListNode head) {
//      过滤排序重复的
//        ListNode curr = head, pre = head;
//        int temp = -1;
//        while (curr.next != null) {
//            if (temp == curr.val) {
//                pre.next = curr.next;
//                curr = pre.next;
//            } else {
//                pre = curr;
//                curr = curr.next;
//                temp = curr.val;
//            }
//        }

//        过滤未排序的
        Set<Integer> set = new HashSet<>();
        ListNode curr = head, pre = head;
        while (curr != null) {
            if (set.add(curr.val)) {
                pre = curr;
                curr = curr.next;
            } else {
                pre.next = curr.next;
                curr = pre.next;
            }
        }
        return head;
    }

    static int[] reversePrint(ListNode head) {
        ListNode curr = head, pre = null;
        int len = 0;
        while (curr != null) {
            ListNode temp = curr.next;
            curr.next = pre;
            pre = curr;
            curr = temp;
            len++;
        }
        int[] vals = new int[len];
        for (int i = 0; i < len; i++) {
            vals[i] = pre.val;
            pre = pre.next;
        }
        return vals;
    }

    /**
     * https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof
     * 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
     * <p>
     * 例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
     * <p>
     *  给定一个链表: 1->2->3->4->5, 和 k = 2.
     * <p>
     * 返回链表 4->5.
     *
     * @createby twj on 2021/8/26 9:39
     */
    static ListNode getKthFromEnd(ListNode head, int k) {
        ListNode curr = head;
        int len = 0;

        while (curr != null) {
            curr = curr.next;
            len++;
        }
        len -= k;
        curr = head;
        for (int i = 0; i < len; i++) {
            curr = curr.next;
        }
        return curr;

//        方法2快慢指针
//        ListNode fast = curr;
//        while (k-- > 0) {
//            fast = fast.next;
//        }
//        while (fast != null) {
//            fast = fast.next;
//            curr = curr.next;
//        }
//        return curr;
    }

    /**
     * https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof
     * 给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
     * <p>
     * 返回删除后的链表的头节点。
     * 输入: head = [4,5,1,9], val = 5
     * 输出: [4,1,9]
     * 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
     *
     * @createby twj on 2021/8/26 10:00
     */
    ListNode deleteNode(ListNode head, int val) {

        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode curr = head;
        while (curr != null) {
            if (curr.val == val) {
                pre.next = curr.next;
                curr = pre.next;
            } else {
                pre = curr;
                curr = curr.next;
            }
        }
        return dummy.next;
    }

    /**
     * https://leetcode-cn.com/problems/kth-node-from-end-of-list-lcci/submissions/
     * 实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
     * 输入： 1->2->3->4->5 和 k = 2
     * 输出： 4
     */
    int kthToLast(ListNode head, int k) {
        ListNode curr = head, fast = head;
        while (k-- > 0) {
            fast = fast.next;
        }
        while (fast != null) {
            curr = curr.next;
            fast = fast.next;
        }
        return curr.val;
    }
}
